package jzOffer;

public class Num19 {
    public boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();

        boolean[][] dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=2;i<=n;i+=2){
            if(p.charAt(i-1)=='*'){
                dp[0][i]=dp[0][i-2];
            }
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.'){
                    dp[i][j]=dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    if(dp[i][j-2]){
                        dp[i][j]=true;
                    }else if(s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.'){
                        dp[i][j]=dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}
